4.0.0 时间复杂度和空间复杂度

算法复杂度分为时间复杂度和空间复杂度。
其作用：时间复杂度是指执行这个算法所需要的计算工作量；
而空间复杂度是指执行这个算法所需要的内存空间。

时间和空间（即寄存器）都是计算机资源的重要体现，
而算法的复杂性就是体现在运行该算法时的计算机所需的资源多少。

时间复杂度

算法中基本操作重复执行的次数是问题规模n的某个函数，其时间量度记作：T(n)=O(f(n))，
称作算法的渐近时间复杂度（Asymptotic Time complexity），简称时间复杂度。
一般地，常用最深层循环内的语句中的原操作的执行频度（重复执行的次数）来表示。

O(1) < O(logn) < O(n) < O(n*logn) < O(n^2) < O(n^3)

O(2^n) < O(n!) < O(n^n)

for(i=1;i<=n;i++){
  a++
};
for(i=1;i<=n;i++){
  for(j=1;j<=n;j++){
    a++;
  }
}

1
2
3
4
5
6
7
8

第一个for循环的时间复杂度为o（n），第二个for循环时间复杂度为o（n^2），则整个算法的时间复杂度为o(n^2+n)。
o(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，时间复杂度就为o(1)。

空间复杂度（Space complexity）：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。
记作：S(n) = O(f(n))，其中：n为问题的规模或大小。

存储空间一般包括三个方面：

输入数据所占用的存储空间；指令常数变量所占用的存储空间；辅助（存储）空间。

一般地，算法的空间复杂度指的是辅助空间。